home *** CD-ROM | disk | FTP | other *** search
/ Oh!X 2001 Spring / Oh!X 2001 Spring Special CD-ROM (Japan).7z / Oh!X 2001 Spring Special CD-ROM (Japan) (Track 1).bin / PUZZLE / Puz02 / hex1.c next >
C/C++ Source or Header  |  2000-06-28  |  2KB  |  124 lines
  1. /*
  2.  * hex1.c : パズル「ヘックス」 15 パズルの変形バージョン
  3.  *
  4.  */
  5. /*
  6.  
  7.          １------２
  8.        ／  ＼  ／  ＼
  9.      ３------４------５
  10.        ＼  ／  ＼  ／ 
  11.          ６------０
  12.  
  13. 座標
  14.          ０------１
  15.        ／  ＼  ／  ＼
  16.      ２------３------４
  17.        ＼  ／  ＼  ／ 
  18.          ５------６
  19. */
  20. #include <stdio.h>
  21. #include <string.h>
  22. #include <time.h>
  23.  
  24. #define TRUE  1
  25. #define FALSE 0
  26. #define SIZE  7
  27.  
  28. /* 最大の状態数 7! = 5040 */
  29. #define MAX_STATE 5040
  30.  
  31. /* 隣接リスト */
  32. const char adjacent[SIZE][7] = {
  33.   1, 2, 3, -1, -1, -1, -1,  /* 0 */
  34.   0, 3, 4, -1, -1, -1, -1,  /* 1 */
  35.   0, 3, 5, -1, -1, -1, -1,  /* 2 */
  36.   0, 1, 2,  4,  5,  6, -1,  /* 3 */
  37.   1, 3, 6, -1, -1, -1, -1,  /* 4 */
  38.   2, 3, 6, -1, -1, -1, -1,  /* 5 */
  39.   3, 4, 5, -1, -1, -1, -1   /* 6 */
  40. };
  41.  
  42. /* キュー */
  43. char  state[MAX_STATE + 1][SIZE];      /* +1 はワーク領域 */
  44. char  space_postion[MAX_STATE];
  45. short prev_state[MAX_STATE];
  46. int count = 0;
  47.  
  48. /* 初期状態 */
  49. char init_state[SIZE] = {
  50.   1, 5, 2, 6, 3, 4, 0
  51. };
  52.  
  53. /* 最終状態 */
  54. char final_state[SIZE] = {
  55.   1, 2, 3, 4, 5, 6, 0
  56. };
  57.  
  58. /* 同じ状態があるか */
  59. int check_same_state( int n )
  60. {
  61.   int i;
  62.   for( i = 0; i < n; i++ ){
  63.     count++;
  64.     if( !memcmp( state[i], state[n], SIZE ) ) return TRUE;
  65.   }
  66.   return FALSE;
  67. }
  68.  
  69. /* 結果を出力 */
  70. void print_answer( int n )
  71. {
  72.   int i;
  73.   if( n != 0 ) print_answer( prev_state[n] );
  74.   for( i = 0; i < SIZE; i++ ){
  75.     printf("%d ", state[n][i] );
  76.   }
  77.   printf("\n");
  78. }
  79.  
  80. /* 探索 */
  81. void search( void )
  82. {
  83.   int front = 0, rear = 1, i;
  84.   /* 初期化 */
  85.   memcpy( state[0], init_state, SIZE );
  86.   space_postion[0] = 6;
  87.   prev_state[0] = -1;
  88.   while( front < rear ){
  89.     int s = space_postion[front];
  90.     int n;
  91.     for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
  92.       /* 状態をコピー */
  93.       memcpy( state[rear], state[front], SIZE );
  94.       /* 移動 */
  95.       state[rear][s] = state[rear][n];
  96.       state[rear][n] = 0;
  97.       space_postion[rear] = n;
  98.       prev_state[rear] = front;
  99.       if( !memcmp( state[rear], final_state, SIZE ) ){
  100.     print_answer( rear );
  101.     printf("状態数 %d 個\n", rear );
  102.     return;
  103.       } else if( !check_same_state( rear ) ){
  104.     /* 登録 */
  105.     rear++;
  106.       }
  107.     }
  108.     front++;
  109.   }
  110. }
  111.  
  112. int main()
  113. {
  114.   int start, end;
  115.   start = clock();
  116.   search();
  117.   end = clock();
  118.   printf("比較回数 %d, 時間 %d \n", count, end - start );
  119.   return 0;
  120. }
  121.  
  122. /* end of file */
  123.  
  124.